This invention relates to machine vision and, more particularly, to methods and apparatus for template matching.
Template matching is a fundamental operation in machine vision. It is used to determine the location of a mark, object or other template in an image. For example, in an industrial assembly operation, machine vision may be employed to determine the position of a part based on the position of an imprinted logo. To this end, an image of the part (i.e., the candidate image) is analyzed to determine the location of an image of the mark (i.e., the template image). Once determined, that location is passed to the assembly equipment for placement of the part.
The art provides many template matching schemes. Many of these operate by applying a correlation function--or other matching function--to determining a degree of similarity between the template image at each location in the candidate image. In one simple scheme, the such a match-scoring function is applied at all locations in the candidate. The resulting scores are compared with one another to find a peak, the position of which is taken as the position of the template in the candidate image. According to a more complex schemes, a "hill climbing" technique is used reduce the number of locations at which the match-scoring function must be applied. There, the function is applied only in an "uphill" direction, i.e., the direction that leads to increasing similarity metrics or scores.
In a 4-way hill climbing system, the match-scoring function is applied in four directions from each new point in the image: north, south, east, and west. In an 8-way system, the function in applied in eight directions: north, northeast, east, southeast, south, southwest, west, and northwest. Results are more rapidly achieved by a 4-way system, but they are not as reliable as those of an 8-way system.
A problem with prior art template matching techniques, such as the 4-way and 8-way searches, is that they fail to identify correctly the locations of all templates. Sometimes, they identify a corresponding peak score at the wrong location in the candidate. At other times, they fail to find any peak at all.
An object of this invention therefore is to provide improved methods and apparatus for template matching. More particularly, an object is to provide methods and apparatus for template matching that correctly identify the location of a template in a candidate image, regardless of the shape of the template or its orientation in the candidate.
Still another object is to provide such methods and apparatus that are faster and more accurate than the prior art hill climbing techniques.
Yet another object is to provide methods and apparatus for template matching that can be implemented cost effectively in a variety of environments.
These and other objects of the invention are evident in the discussion that follows.